package cn.kent.simple;


/**
 * 110. 平衡二叉树
 * 判断左右子树两个子树的高度差的绝对值不超过 1 。
 */
public class IsBalanced {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        System.out.println(isBalanced(root));
    }

    /**
     * 自底向上的递归
     * 先遍历到当前节点，递归判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡，
     * 如果一棵子树是平衡的，则返回其高度(高度一定是非负整数)，否则返回-1。如果存在一棵子树不平衡，则整个二叉树肯定不平衡。
     */
    public static boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public static int height(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
